#include <iostream>
#include <cstdlib>
#include <ctime>
#include "../tools/SpeedProbe.h"

void swap(int* A, int i, int j)
{
  if ( i==j)
    return;

  int tmp = A[i];
  A[i] = A[j];
  A[j] = tmp;

  return;
}

int random(int l, int h)
{
  return l + rand()%(h - l + 1);
}

void quicksort(int *A, int l, int u)
{
  int i, m;

  if ( l >= u )
    return;

  m = l;
  
  swap( A, l, random( l, u ) );
  for ( i = l+1; i <= u; i++ )
    if ( A[i] < A[l] )
      swap( A, ++m, i);

  swap(A, m, l);

  quicksort(A, l, m-1);
  quicksort(A, m+1, u);

  return;
}

void quicksort2(int *A, int l, int u)
{
  int i, j;

  if ( l >= u )
    return;

  i = l;
  j = u+1;
  
  swap( A, l, random( l, u ) );

  while(1){
    do i++; while( i <= u && A[i] < A[l] );
    do j--; while( A[j] > A[l] );
    if( i > j )
      break;
    swap( A, i, j );
  }
  
  swap(A, j, l);
  quicksort2(A, l, j-1);
  quicksort2(A, j+1, u);

  return;
}

void print_array(int *A, int size)
{
  for ( int i = 0; i < size; i++)
    printf("%d\t", A[i]);

  return;
}

int main()
{
  int num = 10000;
  int *A = new int[num];
  srand(time(0));
  for( int i = 0; i < num; i++ )
	A[i] = 2;
  
  pzy::tools::SpeedProbe sp;
  sp.begin();
  quicksort2(A, 0, num-1);
  sp.end();
  printf( "time: %lfs\n", sp.timeSpan() );
  
  //  print_array(A, num);
  delete[] A;
  return 0;
}

